High-Efficiency Video Coding (HEVC) is a new international video coding standard that is being developed by the Joint Collaborative Team on Video Coding (JCT-VC). HEVC is based on the hybrid block-based motion-compensated DCT-like transform coding architecture. The basic unit for compression, termed Coding Unit (CU), is a 2N×2N square block, and each CU can be recursively split into four smaller CUs until a predefined minimum size is reached. Each CU contains one or multiple Prediction Units (PUs). The PU sizes can be 2N×2N, 2N×N, 2N×nU, 2N×nD, N×2N, nL×2N, nR×2N, or N×N, where 2N×N, 2N×nU, 2N×nD and N×2N, nL×2N, nR×2N correspond to horizontal and vertical partition of a 2N×2N PU with symmetric or asymmetric PU size division respectively.
To further increase the coding efficiency of motion vector coding in HEVC, the motion vector competition (MVC) based scheme is applied to select one motion vector predictor (MVP) among a given MVP candidate set which includes spatial and temporal MVPs. There are three inter-prediction modes including Inter, Skip, and Merge in the HEVC test model version 3.0 (HM-3.0). The Inter mode performs motion-compensated prediction with transmitted Motion Vector Differences (MVDs) that can be used together with MVPs for deriving motion vectors (MVs). The Skip and Merge modes utilize motion inference methods (MV=MVP+MVD where MVD is zero) to obtain the motion information from spatial neighboring blocks (spatial candidates) or temporal blocks (temporal candidates) located in a co-located picture. The co-located picture is the first reference picture in list 0 or list 1, which is signaled in the slice header.
When a PU is coded in either Skip or Merge mode, no motion information is transmitted except for the index of the selected candidate. In the case of a Skip PU, the residual signal is also omitted. For the Inter mode in HM-3.0, the Advanced Motion Vector Prediction (AMVP) scheme is used to select a motion vector predictor among an AMVP candidate set including two spatial MVPs and one temporal MVP. As for the Merge and Skip mode in HM-3.0, the Merge scheme is used to select a motion vector predictor among a Merge candidate set containing four spatial MVPs and one temporal MVP.
For the Inter mode, the reference picture index is explicitly transmitted to the decoder. The MVP is then selected among the candidate set for a given reference picture index. FIG. 1 illustrates the MVP candidate set for the Inter mode according to HM-3.0, where the MVP candidate set includes two spatial MVPs and one temporal MVP:                1. Left predictor (the first available MV from A0 and A1),        2. Top predictor (the first available MV from B0, B1, and Bn+1), and        3. Temporal predictor (the first available MV from TBR and TCTR).        
A temporal predictor is derived from a block (TBR or TCTR) in a co-located picture, where the co-located picture is the first reference picture in list 0 or list 1. The block associated with the temporal MVP may have two MVs: one MV from list 0 and one MV from list 1. The temporal MVP is derived from the MV from list 0 or list 1 according to the following rule:                1. The MV that crosses the current picture is chosen first, and        2. If both MVs cross the current picture or both do not cross, the MV with the same reference list as the current list will be chosen.        
In HM-3.0, if a particular block is encoded in the Merge mode, an MVP index is signaled to indicate which MVP among the MVP candidate set is used for this block to be merged. To follow the essence of motion information sharing, each merged PU reuses the MV, prediction direction, and reference picture index of the selected candidate. It is noted that if the selected MVP is a temporal MVP, the reference picture index is always set to the first reference picture. FIG. 2 illustrates the MVP candidate set for the Merge mode according to HM-3.0, where the MVP candidate set includes four spatial MVPs and one temporal MVP:                1. Left predictor (Am),        2. Top predictor (Bn),        3. Temporal predictor (the first available MV from TBR or TCTR),        4. Above-right predictor (B0), and        5. Below-left predictor (A0).        
In HM-3.0, a process is utilized in both Inter and Merge modes to avoid an empty candidate set. The process adds a candidate with a zero MV to the candidate set when no candidate can be inferred in the Inter, Skip or Merge mode.
Based on the rate-distortion optimization (RDO) decision, the encoder selects one final MVP for Inter, Skip, or Merge modes from the given MVP list and transmits the index of the selected MVP to the decoder after removing redundant MVPs in the list. However, because the temporal MVP is included in the MVP list, any transmission error may cause parsing errors at the decoder side and the error may propagate. When an MV of a previous picture is decoded incorrectly, a mismatch between the MVP list at the encoder side and the MVP list at the decoder side may occur. Therefore, subsequent MV decoding may also be impacted and the condition may persist for multiple subsequent pictures.
In HM-4.0, in order to solve the parsing problem related to Merge/AMVP in HM-3.0, fixed MVP list size is used to decouple MVP list construction and MVP index parsing. Furthermore, in order to compensate the coding performance loss caused by the fixed MVP list size, additional MVPs are assigned to the empty positions in the MVP list. In this process, Merge index is coded using truncated unary codes of fixed length equal to 5 or less, and AMVP index is coded using fixed length equal to 2 or less.
Another change in HM-4.0 is the unification of MVP positions. Both Merge and Skip use the same positions shown in FIG. 6.
Additional bi-predictive Merge candidates are created using original Merge candidates. The additional candidates are divided into three candidate types:                Combined bi-predictive Merge candidate (candidate type 1)        Scaled bi-predictive Merge candidate (candidate type 2)        Zero vector Merge/AMVP candidate (candidate type 3)        
In candidate type 1, combined bi-predictive Merge candidates are created by combining original Merge candidate. Two candidates in original candidates are used to create bi-predictive Merge candidates. An example of the derivation process of combined bi-predictive Merge candidate is shown in FIGS. 3A-C, where mvL0_A(uni) refers to a motion vector mvL0 in list 0 with the reference picture index refIdxL0 in list 0, and mvL1_B(uni) refers to a motion vector mvL1 in list 1 with the reference picture index refIdxL1 in list 1. The original candidates are used to generate combined bi-predictive candidates as indicated by arrows 310 and 320. FIG. 3A illustrates the original Merge candidate list and FIG. 3B illustrates the Merge candidate list after adding combined candidates.
In candidate type 2, scaled bi-predictive Merge candidates are created by scaling original Merge candidates. One of the original candidates is used to create bi-predictive Merge candidates. The selected candidate corresponds to a motion vector mvLX with the reference picture index refIdxLX in list X, where X can be 0 or 1. For example, one candidate A is uni-predictive in list 0 with motion vector mvL0_A and reference picture index ref0. In order to derived the scaled candidate, ref0 is copied to reference index ref0′ in list 1 first. Then, mvL0′_A is calculated by scaling mvL0_A according to picture distance of current frame to ref0 and picture distance of current frame to ref0′. The bi-predictive Merge candidate, having mvL0_A and ref0 in list 0 and mvL0′_A and ref0′ in list 1, are then created and added into Merge candidate list. FIGS. 4A-C illustrate an example of the derivation process of the scaled bi-predictive Merge candidate. FIG. 4A and FIG. B correspond to the original Merge candidate list and the Merge list after adding scaled candidates respectively, where the corresponding Merge candidate derivations are indicated by arrows 410 and 420. FIG. 4C illustrates the Merge candidate derivations indicated by arrows 410 and 420 along with related reference pictures.
In candidate type 3, zero-vector Merge candidates and zero-vector AMVP candidates are created by combining zero vectors and reference index that can be referred. FIGS. 5A-D illustrates an example of adding Zero vector Merge candidates and zero vector AMVP candidates. FIG. 5A and FIG. 5B illustrate the original Merge candidate list and the Merge candidate list after adding zero-vector candidates respectively. The added zero-vector candidates are indicated by the dashed box 510. FIG. 5C and FIG. 5D illustrate the original AMVP candidate list and the AMVP candidate list after adding zero-vector candidates respectively. The added zero-vector candidates are indicated by the dashed boxes 520 and 530 for list 0 and list 1 respectively. If a zero-vector candidate is not duplicated, it is added to the respective Merge and AMVP candidate set.
For AMVP in HM-4.0 FIG. 6 illustrates the neighboring PUs configuration to derive the spatial and temporal MVPs for both AMVP and Merge. In AMVP, the left MVP is the first available motion vector between A0 and A1. The top MVP is the first available motion vector among B0, B1 and B2. The temporal MVP is the first available motion vector between TBR and TCTR. TBR is used first and if TBR is not available and otherwise TCTR is used instead. If the left MVP is not available and the top MVP is not a scaled MVP, the second top MVP can be derived if there is a scaled MVP among B0, B1, and B2. The number of MVPs in AMVP candidate set is 2 in HM-4.0. Therefore, after two spatial MVPs and one temporal MVP are derived, only the first two MVPs will be included in the candidate set. If the number of available MVPs is smaller than two after removing redundancy, then zero-vector candidates are added to the candidate set.
For Merge mode in HM-4.0, the MVP candidate derivation uses the same neighboring block configuration as shown in FIG. 6. Up to four spatial MVPs are derived from A0, A1, B0 and B1, and one temporal MVP is derived from TBR or TCTR. TBR is used first if TBR is not available and otherwise TCTR is used instead. If any of the four spatial MVPs is not available, the block B2 is then used to derive MVP as a replacement. After the four spatial MVPs and one temporal MVP are derived, redundancy is checked and any redundant MVP will be removed. If the number of available MVPs is smaller than five after removing redundancy, three types of additional candidates are derived and added to the candidate set.
As illustrated above, the fixed-size Merge/AMVP candidate sets are used in HM-4.0 to overcome the issue associated with parsing error. Moreover, new MVPs are added to the candidate set after removing redundant MVPs in order to improve coding efficiency. However, the MVP candidate derivation for HM-4.0 does not necessarily provide a complete full set of MVP candidates. The number of MVPs in the candidate set may be less than the fixed target size specified. When a parsing error occurs, the encoder and decoder may have different MVP list. If the encoder sends an MVP index pointing to an empty space, mismatch between the encoder and decoder may occur if the encoder and decoder have different MVP lists. The state of mismatch may persist and cause error propagation in the decoder. Accordingly, it is desirable to develop methods of generating additional MVM candidates that can always result in a complete full MVP candidate set.